\documentclass[11pt]{report}
\usepackage{stylefiles/smstc_mod,stylefiles/probability,color,mathrsfs}
%\usepackage{showkeys}
%\usepackage{epsfig}
%% amsmath, amssymb, cite, fancybox, graphicx, ifthen, minitoc, url, xspace
\Streamname{Probability}  
\Unitname{Lecture} 
\Thisyear{2007/08}  
\AuthorFt{}

\theoremstyle{definition}
\newtheorem{exe}{\bf EXERCISE}
\def\N{\mathbb{N}}
\def\Z{\mathbb{Z}}
\def\Q{\mathbb{Q}}
\def\R{\mathbb{R}}
\def\C{\mathbb{C}}
\def\FF{\mathscr{F}}
\def\GG{\mathscr{G}}
\def\HH{\mathscr{H}}
\def\DD{\mathscr{D}}
\def\CC{\mathscr{C}}
\def\RR{\mathscr{R}}
\def\G{\mathbb{G}}
\def\H{\mathbb{H}}
\def\xx{\widehat{x}}
\def\XX{\widehat{X}}
\def\AA{\mathscr{A}}
\def\SS{\mathscr{S}}
\def\TT{\mathscr{T}}
\def\BB{\mathscr{B}}
\def\VV{\mathscr{V}}
\def\LL{\mathcal{L}}
\def\NN{\mathcal{N}}
\def\Qr{\mathbf{Q}}
\renewcommand{\phi}{\varphi}
\renewcommand{\epsilon}{\varepsilon}
\newcommand{\1}{{\text{\Large $\mathfrak 1$}}}
\renewcommand{\comp}{\raisebox{0.1ex}{\scriptsize $\circ$}}
\newcommand{\cadlag}{{c\`adl\`ag} }
\renewcommand{\var}{\operatorname{var}}
\newcommand{\proj}{\operatorname{proj}}
\renewcommand{\cov}{\operatorname{cov}}
\renewcommand{\limsup}{\varlimsup}
\renewcommand{\liminf}{\varliminf}
\renewcommand{\d}{\text{\rm\,d}}
\newcommand{\eqdist}{\stackrel{\text{d}}{=}}
\newcommand{\dirac}{\text{\large $\mathfrak d$}}
\newcommand{\Ri}{\Rightarrow}
\def\iid{{i.i.d.}\xspace}
\def\jid{{i.i.d.}}
\def\ie{{i.e.}\xspace}
\def\eg{{e.g.}\xspace}
%A \xrightarrow[n]{} 0
\def\bigtimes{\text{\LARGE$\times$}}
\def\xor{\text{\footnotesize$\bigtriangleup$}}
\def\prob{\operatorname{\bf prob}}
\def\no{\noindent}

%\parskip \smallskipamount
%\parindent 5mm


\begin{document} \initdoc 




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{unit}{5}{Important special distributions }
% SYLLABUS:
%5.  Important special distributions.                                    TK
%      Binomial,	DONE
% Poisson,	DONE
% geometric,	DONE
% uniform, DONE IN CHAPTER 3
% exponential DONE
% and normal  distributions: DONE IN CHAPTER 3
% definitions, properties and the relations between them.	DONE


\section{Binomial, Poisson, and multinomial}
Consider the coin tossing experiment, i.e.\ consider a sequence
$\xi_1, \xi_2, \ldots$ of i.i.d.\ random variables with
\[
\Pr (\xi_1=1)=p, \quad \Pr(\xi_1=0)=1-p.
\]
The law of 
\[
S_n = \xi_1 + \cdots + \xi_n
\]
is called Binomial with parameters $n$ and $p$.
{From} this we have
\[
\E S_n = n p, \quad \var S_n = n \var \xi_1 = np(1-p),
\]
and, since $\xi_{n+1} + \xi_{n+m}$ is Binomial with parameters
$m$ and $p$, and independent of $S_n$, we have that the sum
of two independent Binomial random variables with the same $p$
is again Binomial.
We also have
\[
\Pr(S_n=k) = \binom{n}{k} p^k (1-p)^{n-k}, \quad
k=0,1,\ldots, n,
\]
and, from the Binomial theorem,
\[
\E e^{\theta S_n} = (p e^\theta + 1-p)^n.
\]
\begin{exe}
Compute the moment generating function of $n^{-1/2}(S_n - \E S_n)$
and show that, as $n \to \infty$, it converges to the
a function of the form $e^{-c \theta^2}$.
(This is moment generating function of a Gaussian random variable).
\end{exe}
\begin{exe}
Use Chernoff's inequality to estimate $\Pr(S_n > n(p+x))$
for $x > 0$.
\end{exe}

By letting $p$ vary with $n$ and taking limits we obtain a
different fundamental law, the Poisson  law.
Specifically,
\begin{lemma}
If $p_n = \frac{\lambda}{n} + o(1/n)$, as $n \to \infty$, then
\[
\Pr(S_n=k) \to \frac{\lambda^k}{k!} e^{-\lambda},
\]
for all $k = 0,1,2, \ldots$.
\end{lemma}
\begin{proof}
Use Stirling's formula.
\end{proof}

This is the Poisson law with parameter $\lambda$. The Poisson law
is fundamental when, roughly speaking,
we deal with independent rare events.

Let $X$ be a Poisson random variable. Then
We have
\[
\E e^{\theta X} = \sum_{k=0}^\infty \frac{(\lambda e^{\theta})^k}{k!} 
e^{-\lambda} = e^{\lambda (e^\theta-1)} .
\]
Differentiating a couple of times, we find
\[
\E X = \lambda, \quad \var X = \lambda.
\]
Furthermore,
\begin{lemma}
If $X_1, X_2, \ldots$ are independent Poisson random variables
with parameters $\lambda_1, \lambda_2, \ldots$ such that
$\sum \lambda_k < \infty$ then $\sum_k X_k$ is Poisson
with parameter $\sum_k \lambda_k$.
\end{lemma}
\begin{proof}
We prove this for a finite number $n$ of random variables (which
is enough by the way we construct a probability on
an infinite product). The moment generating function
of $X_1 + \ldots + X_n$ is
\[
\prod_{k=1}^n e^{\lambda_k (e^\theta-1)}
= e^{(e^\theta-1) \sum_{k=1}^n \lambda_k}
\]
and this is the moment generating function of a Poisson law
with parameter $\sum_k \lambda_k$.
\end{proof}

Next we consider conditional probabilities:
\begin{lemma}
Suppose that $X_1, X_2$ are independent Poisson with parameters
$\lambda_1, \lambda_2$. Then, conditional on $X_1+X_2=n$, we
have that $X_1$ is Binomial with parameters $n$, 
$\lambda_1/(\lambda_1+\lambda_2)$.
\end{lemma}
\begin{proof}
Elementary conditioning: For $0 \le k \le n$,
\begin{gather*}
\Pr(X_1 = k | X_1+X_2=n) =
\frac{\Pr(X_1=k, X_2=n-k)}{\Pr(X_1+X_2=n)}\\
= \frac{\displaystyle \frac{\lambda_1^k}{k!} e^{-\lambda_1}
~ \frac{\lambda_2^{n-k}}{(n-k)!} e^{-\lambda_2}}
{\displaystyle \frac{(\lambda_1+\lambda_2)^n}{n!} e^{-\lambda_1-\lambda_2}}
\\
= \binom{n}{k} \left(\frac{\lambda_1}{\lambda_1+\lambda_2}\right)^k
\left(\frac{\lambda_2}{\lambda_1+\lambda_2}\right)^{n-k}.
\end{gather*}
\end{proof}

Generalising this, we have:
\begin{lemma}
Suppose that $X_1, X_2, \ldots, X_d$ are independent Poisson
with parameters $\lambda_1, \lambda_2, \ldots, \lambda_d$,
respectively. 
Then, conditionally on 
$\sum_k X_k = n$, the random vector $(X_1, \ldots, X_d)$ has
law given by
\[
\Pr(X_1=n_1, \ldots, X_d = n_d \mid \sum_k X_k = n)
= \binom{n}{n_1, \ldots, n_d}
\left(\frac{\lambda_1}{\lambda}\right)^{n_1}
\cdots
\left(\frac{\lambda_d}{\lambda}\right)^{n_d},
\]
where $(n_1, \ldots, n_d)$ are nonnegative integers with sum equal to $n$,
and $\lambda=\sum_k \lambda_k$,
and where
\[
\binom{n}{n_1, \ldots, n_d} = \frac{n!}{n_1! \cdots n_d!}
\]
\end{lemma}
\begin{exe}
Show this.
\end{exe}

The symbol $\displaystyle \binom{n}{n_1, \ldots, n_d}$ 
is the multinomial coefficient
since it appears in the algebraic identity known as multinomial theorem:
\[
(x_1 + \cdots + x_d)^n = \sum_{} \binom{n}{n_1, \ldots, n_d}
x_1^{n_1} \cdots x_d^{n_d}.
\]
The sum is taken over all nonnegative integers
$(n_1, \ldots, n_d)$, with sum equal to $n$.

The random variable $(X_1, \ldots, X_d)$ with values in $\Z^d_+$
is said to have a multinomial distribution with
parameters $d, n, p_1, \ldots, p_d$ (where $p_1+\cdots + p_d=1$, so
one of them is superfluous) if
\[
\Pr(X_1=n_1, \ldots, X_d = n_d) 
= \binom{n}{n_1, \ldots, n_d} p_1^{n_1} \cdots p_d^{n_d},
\]
where $(n_1, \ldots, n_d)$ are nonnegative integers with sum equal to $n$,

Of course, a multinomial distribution with parameters $2, n, p, 1-p$
is a binomial distribution with parameters $n, p$.


\section{Thinning}
Suppose an urn contains $n$ balls. There are $d$ colours available.
Let the colours be denoted by $c_1, c_2, \ldots, c_d$.
To each ball assign colour $c_i$ with probability $p_i$,
independently from ball to ball. Let $S^i_n$ be the number
of balls that have colour $c_i$, $1 \le i \le d$.
It is easy to see that $(S^1_n, \ldots, S^d_n)$ has
a multinomial law:
\[
\Pr(S^1_n = k_1 , \ldots, S^d_n=k_d) =
\binom{n}{k_1, \ldots, k_d} p_1^{k_1} \cdots p_d^{k_d},
\]
where $(k_1, \ldots, k_d)$ are nonnegative integers summing
up to $n$.
Clearly,
\[
S^1_n + \cdots S^d_n = n,
\]
so the random variable $S^1_n, \ldots, S^d_n$ cannot be independent.
The question is:
\begin{quote}
Suppose that the number of balls is itself a random variable, independent
of everything else. Is there a way to choose the law of this random
variable so that the above variables are independent?
\end{quote}
To put the problem in precise mathematical terms, let
$\xi_1, \xi_2, \ldots$ be i.i.d.\ random colours, i.e.\ random
variables taking values in $\{c_1, \ldots, c_d\}$ such that
\[
\Pr(\xi_1 = c_i) = p_i, \quad 1 \le i \le d.
\]
Let
\[
S^i_n := \sum_{k=1}^n \1(\xi_k=c_i).
\]
(In physical terms, $S^i_n$ denotes precisely what we talked about earlier
using a more flowery language.)
Now, independent of the sequence $\xi_1, \xi_2, \ldots$, let $N$
be a random variable with values in $\Z_+$. The problem is
to find its law so that
\[
\text{$S^1_N, \ldots, S^d_N$ are independent random variables. 
\qquad\qquad  ($\star$)}
\]
It turns out that this is a characterising property of the Poisson law.
We will contend ourselves by proving one direction:
\begin{lemma}
If $N$ is Poisson then ($\star$) holds.
Moreover, if $N$ has expectation $\lambda$, then
$S^i_N$ is also Poisson with expectation $\lambda p_i$.
\end{lemma}
\begin{exe}
Prove the last lemma.
\end{exe}



\section{Geometric}
A random variable $X$ with values in $\N$ is geometric if
it has the memoryless property:
\begin{quote}
For each $k \in \N$, the conditional distribution of $X-k$
given $\{X > k\}$ is the same as the distribution of $X$:
\[
\Pr(X-k = n | X > k) = \Pr(X=n).
\]
\end{quote}
Think of $X$ as a random time, e.g.\ the day on which a certain
volcano will erupt. The property above says that if by day $k$
the volcano has not erupted then the remaining time $X-k$ has
the same law as $X$, no matter how large $k$ is.
\begin{lemma}
If $q=\Pr(X>1)$ then 
\[
\Pr(X > k) = q^k, \quad k \in \N
\]
and 
\[
\Pr(X=k) = p q^{k-1},
\]
where $p=1-q$.
\end{lemma}
\begin{proof}
By the property of $X$,
\[
\Pr(X > k+n| X >k) = \Pr(X > n),
\]
for all $k, n$, which means that
\[
\Pr(X>k+1) = \Pr(X>k) \Pr(X>1).
\]
Iterating this, we find
\[
\Pr(X>k) = \Pr(X>1)^k, \quad k = 0,1,\ldots.
\]
\end{proof}

People refer to $X$ as geometric with parameter $p$.
The terminology is not standard because other people refer to $X-1$
(which also has the memoryless property but takes values in
$\Z_+$) as geometric with parameter $q$.
A matter of taste, really.

It is easy to see that
\begin{lemma}
If $X$ is geometric in $\N$ with $\Pr(X=1)=p$ then
\[
\E X = 1/p, \quad \var X = (1-p)/p^2,
\quad 
\E e^{\theta X} = \frac{p e^\theta}{1-(1-p)e^\theta}.
\]
\end{lemma}
\begin{exe}
Do all that.
\end{exe}

A concrete way to get a geometric random variable is
by considering $\xi_1, \xi_2, \ldots$ to be i.i.d.\
with
\[
\Pr(\xi_1=1)=1-\Pr(\xi_1=0)=p
\]
and by letting
\[
X = \inf\{k \ge 1:~ \xi_k=1\}.
\]
We have $\Pr(X< \infty) =1$, so
\[
X = \min\{k\ge 1:~ \xi_k=1\}
\]
and 
\[
\Pr(X > k) = \Pr(\xi_1= \cdots= \xi_{k}=0) = (1-p)^k,
\]
as required.

We have that
\begin{lemma}
If $X_1, X_2, \ldots, X_d$ are independent and geometric
then $X = \min(X_1, \ldots, X_d)$ is geometric.
\end{lemma}
\begin{proof}
\begin{gather*}
\Pr(X > k) = \Pr(X_1 >k, \ldots, X_d > k)\\
= \Pr(X_1 >k) \cdots \Pr(X_d > k) 
\\
= q_1^k \cdots q_d^k =
(q_1\cdots q_d)^k.
\end{gather*}
\end{proof}
\begin{exe}
Let $X, Y$ be independent and geometric.
Show that 
\[
\Pr(X-Y > n | X > Y) = \Pr(X > n),
\]
for all $n$, and interpret the formula.
\end{exe}



\section{Uniform}
We have already seen, in detail, how to construct a uniform
random variable, from first principles. Recall that $U$ is
uniform in the interval $[0,1]$ if $\Pr(U\le x) = x$, $0 \le x \le 1$.
More generally, 
\begin{quote}
$X$ is uniform in $[a,b]$ if, for
all intervals $I$, the probability $\Pr(X \in I)$ is proportional to the 
length of $I$.
\end{quote}
Of course, if $X$ is uniform in $[a,b]$, then $cX+d$
is uniform in the interval with endpoints $ca+d$ and $cb+d$.

Recall that if $F$ is a distribution function 
and $U$ is uniform in $[0,1]$ then $F^{-1}(U)$ is
a random variable with distribution function $F$.

\begin{lemma}
Let $p_1, \ldots, p_d$ be positive numbers adding up to $1$.
Split the interval $[0,1]$ into consecutive intervals $I_1, \ldots, I_d$
of lengths $p_1, \ldots, p_d$, respectively. Let $U_1, \ldots, U_n$
be i.i.d.\ uniform in $[0,1]$. Let
\[
S_n^i = \sum_{k=1}^n \1(U_k \in I_i),
\quad 1 \le i \le d.
\]
Then $(S_n^1, \ldots, S_n^d)$ has a multinomial law.
In particular, $S^i_n$ is Binomial with parameters $n, p_i$.
\end{lemma}
\begin{exe}
Show this last lemma.
\end{exe}
\begin{exe}
Let $U_1, \ldots, U_d$ be i.i.d.\ uniform in $[0,1]$.
Compute the probability $\Pr(U_1 < U_2 < \cdots < U_d)$.
\end{exe}
\begin{exe}
Consider a stick of length $1$ and break it into 3 pieces, by
choosing the two break points at random.
Find the probability that the 3 smaller sticks can be joined to form
a triangle.
\end{exe}
\begin{exe}
Pick a random variable $U_1$ uniform in $[0, 1]$.
Let $U_2$ be the midpoint of the interval $[0, U_1]$ or
of $[U_1, 1]$, with equal probability.
Continue in the same manner and define $U_3$ to be the midpoint
of $[0,U_2]$ or of $[U_2, 1]$, with equal probability.
Show that the $x \mapsto \lim_{n\to \infty}\Pr(U_n \le x)$ 
is continuous but not absolutely so.
\end{exe}


\section{Exponential}
A random variable $T$ with values in $\R_+$ is exponential if it
has the memoryless property:
\begin{quote}
For all $t, s > 0$,
\[
\Pr(T-t > s | T > t)= \Pr(T > s).
\]
\end{quote}
\begin{lemma}
If $T$ is exponential then there is $\lambda > 0$ such that
\[
\Pr(T > t) = e^{-\lambda t}, \quad t \ge 0.
\]
\end{lemma}
\begin{proof}
Implicit in the definition is that $\Pr(T > t) > 0$ for all $t$.
Hence $\alpha := \Pr(T>1) \in (0,1)$.
We have
\[
\Pr(T > t+s) = \Pr(T>t) \Pr(T> s)
\]
for all $t,s$.
Using this and induction, we have that, for all $n \in \N$,
\[
\Pr(T > nt) = \Pr(T>t)^n.
\]
This gives that, for all $m \in \N$,
\[
\Pr(T > 1 = m(1/m)) = \Pr(T > 1/m)^m
\]
and so $\Pr(T> 1/m) = \Pr(T>1)^{1/m}$.
Letting $t=1/m$ in the pre-last display,
we have
\[
\Pr(T > n/m) = \alpha^{n/m}.
\]
Now, for $t>0$, let $q_1> q_2> \ldots$ be
rational numbers with $\inf\{q_1, q_2, \ldots\} = t$.
Then 
\[
\Pr(T > t) = \Pr(\cup_k \{T > q_k\})
= \sup_k \Pr(T>q_k) = \sup_k \alpha^{q_k}
= \alpha^{\inf_k q_k} = \alpha^t.
\]
Since $\alpha < 1$, we have $\lambda := -\log \alpha > 0$.
\end{proof}

We say that $T$ is exponential with parameter (rate) $\lambda$.

It is easy to see that
\begin{lemma}
If $T$ is exponential with rate $\lambda$ then $T$ has
density
\[
f(t) = \lambda e^{-\lambda t}, \quad t \ge 0.
\]
Also,
\[
\E e^{\theta T} = \frac{\lambda}{\lambda-\theta},
\]
defined for all $\theta < \lambda$,
and
\[
\E T = 1/\lambda, \quad
\var T = 1/\lambda^2.
\]
\end{lemma}
\begin{proof}
Note that 
\[
\int_0^t f(s) ds = 1-e^{-\lambda t},
\]
showing that $f$ is a density for $T$.
The rest are trivial.
\end{proof}

\begin{lemma}
Let $T_1, T_2, \ldots, T_d$ be independent  exponential random variables
with parameters $\lambda_1, \lambda_2, \ldots, \lambda_d$, respectively.
Then $\min(T_1, \ldots, T_d)$ is exponential with parameter
$\lambda_1+\cdots+\lambda_d$.
\end{lemma}
\begin{proof}
\[
\Pr(\min(T_1, \ldots, T_d)>t) = \Pr(T_1>t) \cdots \Pr(T_d > t).
\]
\end{proof}

Whereas an exponential is the natural analogue of a geometric,
in that they are both memoryless, the former also enjoys the important
scaling property:
\begin{quote}
If $T$ is exponential with rate $\lambda$ then, for any $c > 0$,
 $cT$ is exponential with rate $\lambda/c$,
\end{quote}
and this is obvious.

\begin{exe}
Let $T_1, T_2, \ldots, T_d$ be independent  exponential random variables
all with rate $1$. Show that 
\[
\text{law of } \max(T_1, \ldots, T_d) =
\text{ law of } \left(T_1 + \frac{T_2}{2}+ \cdots + \frac{T_d}{d}\right).
\]
\end{exe}

Another relation between geometric and exponential is
the following: Let $p$ be very small. Let $X$ be geometric
with parameter $p$. Consider a scaling of $X$ by $p$, i.e.\ the
random variable $pX$ which takes values $p,2p,3p,\ldots$.
Then the law of $pX$ converges to an exponential law
with rate $1$:
\begin{lemma}[R\'enyi]
For $X$  geometric with parameter $p$,
\[
\lim_{p \to 0} \Pr(p X > t) = e^{-t}, \quad t >0.
\]
\end{lemma}
\begin{proof}
$\Pr(pX >t) = \Pr(X > t/p)$,
and, since $X$ is an integer, 
\[
\Pr(X > t/p) = \Pr(X \ge \lceil t/p \rceil)
= (1-p)^{\lceil t/p \rceil+1}.
\]
Since $\lim_{n \to \infty}(1+n^{-1})^n = e$,
we have that the last expression converges to $e^{-t}$ as $p \to 0$.
\end{proof}


\section{Gaussian (normal) variables}
\subsection{The Gaussian law}
The motivation of the Gaussian probability comes from the 
central limit theorem (which, long time ago, was known
as the ``law of errors''). This was stated, without proof, in \fbox{2.3.2}.
We work heuristically in order to motivate the definitions.
Let $S_n = \xi_1+\cdots + \xi_n$
be the sum of $n$ independent indicator (also
known as Bernoulli) random variables $\xi_i$ with $\Pr(\xi_i=1) = p$ for
all $i$. Let $\widehat S_n = S_n - \E S_n$.
Then, as $n \to \infty$, the distribution function of $\widehat S_n/\sqrt{n}$
converges to an absolutely continuous distribution function
with a famous formula.
Let $X$ be a random variable with such a distribution function.
Note that
\[
\frac{\widehat S_{2n}}{\sqrt{n}} = 
\frac{1}{\sqrt{2}} \frac{\widehat S_n}{\sqrt{n}} +
\frac{1}{\sqrt{2}} \frac{\widehat S'_n}{\sqrt{n}},
\]
where $\widehat S'_n = \xi_{n+1} + \cdots + \xi_{2n}$ is
a random variable with the same law as $\widehat S_n$.
So the distribution of $\frac{\widehat S'_n}{\sqrt{n}}$ will
also converge to the distribution of $X$. Moreover,
$\widehat S'_n$, $\widehat S_n$ are independent.
Therefore, if $X_1, X_2$ are independent random variables
with the same law as $X$, then we expect that
\[
X = \frac{X_1+X_2}{\sqrt{2}}.
\]
Even if we do not know what this famous distribution is, it
should be such that this ``addition law'' holds. {From} this,
we can discover its density. One way to do that is by imposing the
extra assumption (which is not necessary) that the generating
function of $X$ exists for all $\theta$: $M(\theta) = \E e^{\theta X}$.
Then
\[
M(\theta) = M(\theta/\sqrt{2})^2.
\]
Letting $\theta = \sqrt{\eta}$ and taking logarithms, we have
\[
\log M(\sqrt{\eta}) = 2 \log M(\sqrt{\eta/2}).
\]
So, if we temporarily let $m(\eta) = \log M(\sqrt(\eta))$
we have
\[
m(\eta) = 2 m(\eta/2).
\]
So $m(0)=0$ and
with some work, we can actually find that the only 
continuous function satisfying the latter is linear: $m(\eta) = c \eta$.
(This should be geometrically obvious.)
Hence
\[
M(\theta) = e^{c \theta^2}.
\]
We know that the moments of $X$
are given by the derivatives of $M$ at $0$. We find
\[
M'(0) =0, \quad M''(0) = 2c.
\]
So $\E X=0$ (as it should), while $\E X^2 = 2c$.
So $c > 0$. Since $\E X=0$, the second moment is the variance
and we customarily denote it by $\sigma^2$. We arrive at
\[
M(\theta) = e^{\frac{1}{2} \sigma^2 \theta^2}.
\]
We know that there is only one probability distribution with
a given moment generating function. Instead of trying to figure out
which one it is, let us reveal the result and then just verify
that it is correct. We claim that the probability distribution corresponding 
to the last $M$ is absolutely continuous with density
\[
f(x) = C e^{-x^2/2\sigma^2}.
\]
Here, $C$ is such that $\int_\R f(x) dx = 1$.
This is the famous {\sc normal or Gaussian density} with mean $0$ and
variance $\sigma^2$. It is called standard if $\sigma^2=1$.
\begin{exe}
Show that $\int_{-\infty}^\infty e^{\theta x} f(x) dx
=  e^{\frac{1}{2} \sigma^2 \theta^2}$.
(Hint: Complete the square and use the definition of $C$.)
\end{exe}
Now, to find $C$ is a very important thing. It is based on the following:
\begin{lemma}
\[
\int_\R e^{-x^2} dx = \sqrt{\pi}.
\]
(Liouville said that a Mathematician is someone for whom this
integral is obvious.)
\end{lemma}
\begin{exe}
Use Fubini's theorem to write
$\left(\int_\R e^{-x^2} dx\right)^2 =
\int_{\R^2} e^{-x^2-y^2} dx dy$ and do the latter
integral using polar co\"ordinates.
\end{exe}
Using this we find that 
\[
C= \frac{1}{\sqrt{2\pi\sigma^2}}.
\]
Therefore, the standard normal density is
\[
\phi(x)
= \frac{1}{\sqrt{2\pi}} e^{-x^2/2}.
\]
We write $\NN(0,1)$ for the law of a random variable $X$ with standard normal
density. We write $\NN(\mu, \sigma^2)$ for the
law of $\sigma X + \mu$.

\begin{exe}
Show that a density for $\NN(\mu,\sigma^2)$ is
\[
\frac{1}{\sqrt{2\pi\sigma^2}}
\exp\left\{ - \frac{(x-\mu)^2 }{2\sigma^2} \right\}.
\]
\end{exe}

\begin{exe}
Show that if $X_i, i=1, \ldots, d$ are independent
and $X_i$ having law $\NN(\mu_i, \sigma_i^2)$ then
$\sum_{i=1}^d X_i$ has law $\NN(\sum_i \mu_i, \sum_i \sigma_i^2)$.
Therefore linear combinations of independent normal
variables are normal.
\end{exe}



\subsection{The multidimensional Gaussian random vector}
We now pass on to defining a Gaussian (or normal) 
random variable in $\R^d$.
\begin{quote}
We say that $(X_1, \ldots, X_d)$
is Gaussian in $\R^d$ if, for all $a_1, \ldots, a_d \in \R$,
the random variable $a_1 X_1 + \cdots + a_d X_d$ is normal.
\end{quote}
The next lemma shows what the moment generating function
of a normal vector is:
\begin{lemma}
If $(X_1, \ldots, X_d)$ is Gaussian vector with
\[
\mu_j = \E X_j, \quad r_{jk} = \cov(X_j, X_k),
\]
then
\[
\E \exp \sum_{j=1}^d \theta_j X_j
= \exp \left\{
\sum_{j=1}^d \mu_j \theta_j 
+ \frac{1}{2} \sum_{j=1}^d \sum_{k=1}^d r_{jk} \theta_j \theta_k \right\}.
\]
\end{lemma}
\begin{proof}
By definition $\sum_{j=1}^d \theta_j X_j$ should be normal,
i.e.\ have a law $\NN(\mu, \sigma^2)$, for some $\mu, \sigma^2$.
We have
\[
\mu = \E \sum_{j=1}^d \theta_j X_j = \sum_{j=1}^d \mu_j \theta_j,
\quad
\sigma^2 = \cov \sum_{j=1}^d \theta_j X_j 
= \sum_{j=1}^d\sum_{k=1}^d \theta_j \theta_k \cov(X_j, X_k).
\]
\end{proof}

Since the moment generating function of a Gaussian vector
is the exponential of a quadratic form, there is no better way
to express it other than using Linear Algebra. To this end,
we think of the elements $x$ of  $\R^d$  as column vectors.
We use $x'$ to denote transposition, i.e.\ the corresponding row
when $x$ is a column. And, of course, $(x')' = x$.
Consider the mean (column) vector
\[
\mu = (\mu_1, \ldots, \mu_d)'
\]
and the symmetric covariance matrix
\[
R= [r_{jk}].
\]
Write also $X$ for the column with entries $X_1, \ldots, X_d$.
We then have
\[
\E e^{\theta' X} = 
\exp \left\{ \theta' \mu + \frac{1}{2} \theta' R \theta \right\}.
\]
This uniquely defines the law of $(X_1, \ldots, X_d)$.
This law is denoted by $\NN(\mu, R)$, where
$\mu$ is the mean vector and $R$ the covariance matrix.



\begin{lemma}
A Gaussian vector $(X_1, \ldots, X_d)$ is absolutely continuous
if and only if $R$ is invertible. In this case, its
density is given by
\[
f(x) = \frac{1}{\sqrt{(2\pi)^d\det(R)}} \exp\left(-\frac{1}{2}(x-\mu)'R^{-1}(x-\mu)\right)\,.
\]
\end{lemma}
\begin{proof}
Assume $\mu=0$, to ease notation.
Assume $R$ is invertible.
It is easily seen that 
\[
R=\E(XX')
\]
where $X X'$ is a $d \times d$ matrix and $\E(X X')$ is the matrix
formed by taking the expectations of the entries of $X X'$.
This $R$ has two important properties: \\
(i) it is symmetric (obviously); \\
(ii) it is positive semi-definite, i.e.\ the quadratic form
\[
u'Ru=\sum_k\sum_\ell R_{k\ell}u_k u_\ell \ge 0
\]
for all values of
the variables, positive or negative. The reason for the latter is that
$u'Ru $ is the expectation of a non-negative quantity:
\[
u'Ru=u'\E XX'u=\E(X'u)'(X'u) = \E(X'u)^2 \ge 0.
\]
Standard linear algebra
shows that $R$ has exactly $d$ (counting multiplicities) non-negative eigenvalues.
(In fact, they are strictly positive,
due to the invertibility of $R$ which is tantamount to
$\det(R) \ne 0$). 
Furthermore, the eigenvectors can be chosen to be orthonormal.
Letting $U$ be the matrix whose columns are these $d$ orthonormal eigenvectors
and $\Lambda$ the diagonal matrix with the eigenvalues in its diagonal,
we have 
\[
RU = U \Lambda, 
\]
from the very definition of the eigenvectors.
Now 
\[
U'=U^{-1},
\]
hence 
\[
R=U \Lambda U' = U \Lambda^{1/2} \Lambda^{1/2} U' =
P P',
\]
with 
\[
P=U \Lambda^{1/2}.
\]
The matrix $P$ is non-singular and is called
the square root of $R$. We now define new random variables $Z$ by 
\[
X = P Z\,.
\]
The thing to observe is that the covariance matrix of $Z$ is
\[
\cov(Z) = \E ZZ' = \E P^{-1}XX'P'^{-1}=P^{-1}R'P'^{-1}=P^{-1}PP'P'^{-1}=I,
\]
$I$ being the identity matrix. Thus 
\[
\E e^{\theta'Z} = e^{\theta'\theta/2}=
\prod_{j=1}^d e^{\theta_j^2/2} = \prod_{j=1}^d \E e^{\theta_jZ_j},
\]
implying that the components of $Z$ are independent standard normal.
Hence the density $g$ of $Z$ is product:
\[
g(z) = \prod_j \frac{1}{\sqrt{2\pi}} e^{-z_j^2/2}.
\]
Now $X=PZ$, hence its density $f$ is computed easily
by 
\[
f(x) = g(P^{-1}x)/|\det(P)|,
\]
which yields the desired formula.
\end{proof}




If $R$ has determinant zero then it is possible to ``reduce the dimension''
of the random vector $X$ so that the density exists.
In fact,
\begin{lemma}
The support of $X$ is the range of its covariance matrix $R$.
\end{lemma}
\begin{proof}
Suppose that $R$ has rank $r$. Then it has $d-r$ eigenvalues at zero,
so that the matrix $\Lambda$ consists of a $d-r$ size block of zeros and 
the remaining non-zero eigenvalues. Hence now $R = PP'$,
where $P$ is a $d\times r$ matrix with rank $r$. 
We try again to find $Z$ so that 
\[
X=PZ,
\]
where $Z$ is an $r$-dimensional random vector with density.
If we manage to do this we will finish, since the range of $P$ is
the range of $R$. Observing that $P'P$ is an $r\times r$ non-singular matrix,
we pre-multiply by it to get $P'PZ = P'X$, hence $Z=(P'P)^{-1}P'X$.
So if we define $Z$ this way, we see that 
\[
\E ZZ'=
(P'P)^{-1}P'RP(P'P)^{-1} =
(P'P)^{-1}P'PP'P(P'P)^{-1}=I,
\]
i.e.\ $Z$ is a collection of $r$ independent
standard normal variables.
The formula for $Z$ is the formula that solves a full-rank over-estimated
linear system. We usually write $Z = P^+ X$ and call $P^+$ the pseudo-inverse of $P$.
It remains to show that every linear function of $X$ is a linear function of $Z$.
Let \[
F=\lambda'Xa \quad, G=\lambda'PZ
\]
with $Z=P^+X$.
Consider 
\[
F-G=\lambda'(X-PZ).
\]
Then 
\[
\E (F-G)^2 = \E \lambda'(X-PZ)(X'-Z'P')\lambda
=\E \lambda'(XX'-XZ'P'-PZX'+PZZ'P')\lambda.
\]
But 
\[
\E ZX'=(P'P)^{-1}P'\E XX'=(P'P)^{-1}P'PP'=P'.
\]
So 
\[
\E (F-G)^2 = \lambda'(PP'-PP'-PP'+PP')\lambda=0.
\]
\end{proof}

Terminology: If $X$ has law $\NN(0,R)$ with $R$ having rank $r$
then $\sum_j X_j^2$ is called $\chi^2$ with $r$ degrees of freedom.


\subsection{Conditional Gaussian law}
If it appears that we've done a lot of Linear Algebra, then this
is because it is so: 
Dealing with Gaussian random variables (and processes!) 
is mostly dealing with Linear Algebra (or Linear Analysis!).

Without proof, we mention the following:
\begin{lemma}
Let $(X; Y_1, \ldots, Y_d)$ be a Gaussian random variable in $\R^{1+d}$.
Then the conditional law $\Pr(X \in \cdot | Y_1, \ldots, Y_d)$ is
normal with mean $\E(X | Y_1, \ldots, Y_d)$ and deterministic covariance matrix.
Moreover, $\E(X | Y_1, \ldots, Y_d)$ is a linear function of 
$Y_1, \ldots, Y_d)$ and is characterised by the
fact that $X-E(X | Y_1, \ldots, Y_d)$ is independent of 
$(Y_1, \ldots, Y_d)$.
\end{lemma}

\begin{exe}
Let $X, Y$ be independent standard Gaussian variables.
Based on the last part of the lemma above, compute
$\E(X+2Y | 3X-4Y)$.
\end{exe}





\end{unit}

\end{document}



